// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 经典题目：斐波那契数列模型，路径问题

// 技巧：
// dp[] 表多开一个长度，处理数组越界及初始化复杂的问题
// dp[][] 表多开一行，多开一列
// 结合滚动数组优化 - 注意赋值顺序

// 例题 2：
// 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。
// 机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
// 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
// 回机器人能够到达右下角的不同路径数量。
//
//        测试用例保证答案小于等于 2 * 109。
//
//        示例 1：
//
//
//        输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
//        输出：2
//        解释：3x3 网格的正中间有一个障碍物。
//        从左上角到右下角一共有 2 条不同的路径：
//        1. 向右 -> 向右 -> 向下 -> 向下
//        2. 向下 -> 向下 -> 向右 -> 向右
//        示例 2：
//
//
//        输入：obstacleGrid = [[0,1],[0,0]]
//        输出：1
//
//
//        提示：
//
//        m == obstacleGrid.length
//        n == obstacleGrid[i].length
//        1 <= m, n <= 100
//        obstacleGrid[i][j] 为 0 或 1

// 解题思路：
// dp[i][j]: 表示从 1,1 出发 到 i,j 位置的路径数
// dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

public class UniquePathsWithObstacles {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];

        dp[0][1] = 1;

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(obstacleGrid[i - 1][j - 1] == 1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}
